#include <iostream>
#include <vector>
using namespace std;

	class HeapSort
	{
	public:
      HeapSort( vector< int >& li ):m_list(li) { }

		void make_heap()
		{
			int size = m_list.size();
			for( int i = size/2-1; i >= 0; i-- )
				adjust_node(i);
		}

		void adjust_first_node()
		{
			adjust_node( 0 );
		}

	private:
		void adjust_node( int n )
		{
			int l = 2*n + 1;
			int r = 2*n + 2;
			int largest;
			
			if( l < m_list.size() && compare_iter_node( m_list[l], m_list[n] ) )
				largest = l;
			else
				largest = n;

			if( r < m_list.size() && compare_iter_node( m_list[r], m_list[largest] ) )
				largest = r;

			if( largest != n ){
				int tmp = m_list[largest];
				m_list[largest] = m_list[n];
				m_list[n] = tmp;
				adjust_node( largest );
			}
		}

	private:
		inline bool compare_iter_node( const int& a, const int& b ) const
		{
          return a > b;
		}
	private:
        vector< int >& m_list;
	};

void print_vector( vector<int>& li )
{
  for( int i = 0; i < li.size(); i++){
    cout << li[i] << "\t";
  }
}

int main()
{
  vector< int > li;

  for(int i = 0; i<5; i++){
    li.push_back( i );
  }

  HeapSort hs( li );
  hs.make_heap();
  print_vector( li );
  
  return 0;
}
